package com.tucc.hello.leetcode.no1_400.no1_200.no41_60.no52;

import java.util.ArrayList;
import java.util.List;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.totalNQueens(9));
    }

    public int totalNQueens(int n) {
        if (n > 0) {
            solveNQueens(0, n, new ArrayList<>());
        }
        return count;
    }

    public int count = 0;

    public void solveNQueens(int cur, int n, List<Integer> list) {
        if (list.size() == n) {
            count++;
        } else {
            for (int i = 0; i < n; i++) {
                boolean ok = true;
                for (int j = 0; j < cur; j++) {
                    Integer c = list.get(j);
                    if (c.equals(i) || c.equals(i - cur + j)
                            || c.equals(i + cur - j)) {
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    list.add(i);
                    solveNQueens(cur + 1, n, list);
                    list.remove(list.size() - 1);
                }
            }
        }

    }

}
